package com.leetcodehot.problems;

import java.util.Arrays;

public class problems72 {
    /**
     * 记忆化搜索
     */
    /*
    public int minDistance(String word1, String word2) {
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();
        int len1 = charArray1.length;
        int len2 = charArray2.length;
        int[][] memo = new int[len1 + 1][len2 + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(len1 - 1, len2 - 1, charArray1, charArray2, memo);
    }

    private int dfs(int i, int j, char[] charArray1, char[] charArray2, int[][] memo) {
        if (i < 0) {
            return j + 1;
        }
        if (j < 0) {
            return i + 1;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        if (charArray1[i] == charArray2[j]) {
            return memo[i][j] = dfs(i - 1, j - 1, charArray1, charArray2, memo);
        }
        int ans = Integer.MAX_VALUE;
        //删除当前
        ans = Math.min(ans, dfs(i - 1, j, charArray1, charArray2, memo));
        //新增当前
        ans = Math.min(ans, dfs(i, j - 1, charArray1, charArray2, memo));
        //替换当前
        ans = Math.min(ans, dfs(i - 1, j - 1, charArray1, charArray2, memo));
        return memo[i][j] = ans + 1;
    }
     */

    /**
     * 递推
     */
    /*
    public int minDistance(String word1, String word2) {
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();
        int len1 = charArray1.length;
        int len2 = charArray2.length;
        int[][] f = new int[len1 + 1][len2 + 1];
        for (int j = 0; j <= len2; j++) {
            f[0][j] = j;
        }
        for (int i = 0; i < len1; i++) {
            f[i + 1][0] = i + 1;
            for (int j = 0; j < len2; j++) {
                f[i + 1][j + 1] = charArray1[i] == charArray2[j] ? f[i][j] :
                        Math.min(f[i][j + 1], Math.min(f[i + 1][j], f[i][j])) + 1;
            }
        }
        return f[len1][len2];
    }
    */

    /**
     * 一个数组
     * f[i + 1][j + 1] = charArray1[i] == charArray2[j] ? f[i][j] :
     * Math.min(f[i][j + 1], Math.min(f[i + 1][j], f[i][j])) + 1;
     * 对于当前i+1,j+1 需要保留pre = i,j 其他的都可以按正序来处理
     */
    public int minDistance(String word1, String word2) {
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();
        int len1 = charArray1.length;
        int len2 = charArray2.length;
        int[] f = new int[len2 + 1];
        for (int j = 0; j <= len2; j++) {
            f[j] = j;
        }
        for (int i = 0; i < len1; i++) {
            int pre = f[0];
            f[0] = i + 1;
            for (int j = 0; j < len2; j++) {
                int temp = f[j + 1];
                f[j + 1] = charArray1[i] == charArray2[j] ? pre :
                        Math.min(f[j + 1], Math.min(f[j], pre)) + 1;
                pre = temp;
            }
        }
        return f[len2];
    }
}
